/**
 * Created by forcht on 2018/4/30.
 */
public class Solution {
    public boolean canJump(int[] A) {
        boolean[] d=new boolean[A.length];
        d[A.length-1]=true;
        for(int i=A.length-2;i>=0;i--){
            int t=A[i];
            for(int j=i+1;j<=i+t&&j<A.length;j++){
                if(d[j]){
                    d[i]=true;
                    break;
                }
            }
        }
        return d[0];
    }
    //解法二
//    public boolean canJump(int[] A) {
//        int[] dp = new int[A.length+1];
//        dp[A.length - 1] = 1;
//        for (int i = A.length - 2; i >= 0; i--) {
//            int t = i + A[i];
//            if (t > A.length - 1) t = A.length-1;
//            int sum = dp[i+1] - dp[t+1];
//            if (sum > 0) dp[i]=dp[i+1]+1;
//            else dp[i]=dp[i+1];
//        }
//        return dp[0]>dp[1];
//    }
    //解法三
//    public boolean canJump(int[] A) {
//        int max=0;
//        for(int i=0;i<A.length&&max>=i;i++){
//            if(A[i]+i>max)max=A[i]+i;
//        }
//        return max>=A.length-1;
//    }
}
